On fall colorings of graphs.

zbMATH Open1349.05125arXiv0909.2769MaRDI QIDQ2804838FDOQ2804838

Authors: Saeed Shaebani 

Publication date: 4 May 2016

Published in: Ars Combinatoria (Search for Journal in Brave)

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)$.

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

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

zbMATH Keywords

lexicographic productcategorical productfall coloring

Mathematics Subject Classification ID

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

Cited In (7)

• Fall coloring of graphs. I
• Fall colorings on Cartesian products and regular graphs
• Title not available (Why is that?)
• A note on fall colorings of Kneser graphs
• Fall coloring of graphs. II
• Fall coloring on product of cycles and powers
• Graphs with small fall-spectrum

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)