Nordhaus-Gaddum-type relations of three graph coloring parameters
From MaRDI portal
Publication:741774
DOI10.1016/J.DAM.2013.08.043zbMATH Open1300.05099arXiv1209.2202OpenAlexW2100307598MaRDI QIDQ741774FDOQ741774
Authors: Kuo-Ching Huang, Ko-Wei Lih 
Publication date: 12 September 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: Let G be a simple graph. A coloring of vertices of G is called (i) a 2-proper coloring if vertices at distance 2 receive distinct colors; (ii) an injective coloring if vertices possessing a common neighbor receive distinct colors; (iii) a square coloring if vertices at distance at most 2 receive distinct colors. In this paper, we study inequalities of Nordhaus-Guddam type for the 2-proper chromatic number, the injective chromatic number, and the square chromatic number.
Full work available at URL: https://arxiv.org/abs/1209.2202
Recommendations
- On some extremal graph coloring problems of Nordhaus Gaddum class
- Some bounds on the injective chromatic number of graphs
- On Nordhaus-Gaddum type inequalities for the game chromatic and game coloring numbers
- scientific article; zbMATH DE number 500499
- A general approach to distance-two colouring of graphs on surfaces
Cites Work
- List injective colorings of planar graphs
- A survey on labeling graphs with a condition at distance two
- A survey of Nordhaus-Gaddum type relations
- On Complementary Graphs
- Injective colorings of planar graphs with few colors
- Injective coloring of planar graphs
- Injective colorings of graphs with low average degree
- Injective colorings of sparse graphs
Cited In (3)
This page was built for publication: Nordhaus-Gaddum-type relations of three graph coloring parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741774)
