On fall colorings of graphs.

MaRDI QIDQ2804838zbMATHFDO

Authors Saeed Shaebani

Publication date 4 May 2016

Published in Ars Combinatoria (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.2769

zbMATH Keywords

lexicographic productcategorical productfall coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A fall $k$-coloring of a graph $G$ is a proper $k$-coloring of $G$ such that each vertex of $G$ sees all $k$ colors on its closed neighborhood. We denote $mFall(G)$ the set of all positive integers $k$ for which $G$ has a fall $k$-coloring. In this paper, we study fall colorings of lexicographic product of graphs and categorical product of graphs and answer a question of cite{dun} about fall colorings of categorical product of complete graphs. Then, we study fall colorings of union of graphs. Then, we prove that fall $k$-colorings of a graph can be reduced into proper $k$-colorings of graphs in a specified set. Then, we characterize fall colorings of Mycielskian of graphs. Finally, we prove that for each bipartite graph $G$, $mFall(G^c)subseteqchi(G^c)$ and it is polynomial time to decision whether or not $mFall(G^c)=chi(G^c)$.

Recommendations

• Fall coloring of graphs. II
• scientific article; zbMATH DE number 1506511
• On graph fall-coloring -- operators and heredity
• Fall coloring of graphs. I
• Fall colorings on Cartesian products and regular graphs

Cited in

(7)

• Fall coloring of graphs. II
• scientific article; zbMATH DE number 1506511 (Why is no real title available?)
• Fall colorings on Cartesian products and regular graphs
• Fall coloring on product of cycles and powers
• Graphs with small fall-spectrum
• A note on fall colorings of Kneser graphs
• Fall coloring of graphs. I

This page was built for publication: On fall colorings of graphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804838)