On Fall-Colorable Graphs

Shaojun Wang, Fei Wen, Guoxing Wang and Zepeng Li ()
Additional contact information
Shaojun Wang: School of Information Engineering and Artificial Intelligence, Lanzhou University of Finance and Economics, Lanzhou 730020, China
Fei Wen: Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, China
Guoxing Wang: School of Information Engineering and Artificial Intelligence, Lanzhou University of Finance and Economics, Lanzhou 730020, China
Zepeng Li: School of Information Science and Engineering, Lanzhou University, Lanzhou 730000, China

Mathematics, 2024, vol. 12, issue 7, 1-7

Abstract: A fall k -coloring of a graph G is a proper k -coloring of G such that each vertex has at least one neighbor in each of the other color classes. A graph G which has a fall k -coloring is equivalent to having a partition of the vertex set V ( G ) in k independent dominating sets. In this paper, we first prove that for any fall k -colorable graph G with order n , the number of edges of G is at least ( n ( k − 1 ) + r ( k − r ) ) / 2 , where r ≡ n ( mod k ) and 0 ≤ r ≤ k − 1 , and the bound is tight. Then, we obtain that if G is k -colorable ( k ≥ 2 ) and the minimum degree of G is at least k − 2 k − 1 n , then G is fall k -colorable and this condition of minimum degree is the best possible. Moreover, we give a simple proof for an NP-hard result of determining whether a graph is fall k -colorable, where k ≥ 3 . Finally, we show that there exist an infinite family of fall k -colorable planar graphs for k ∈ { 5 , 6 } .

Keywords: fall k-coloring; fall k-colorable graph; computational complexity; domination problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/7/1105/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/7/1105/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:7:p:1105-:d:1371305

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().