Online Coloring and $L(2,1)$-Labeling of Unit Disk Intersection Graphs

DOI10.1137/16M1097821zbMath1395.68341WikidataQ62595888 ScholiaQ62595888MaRDI QIDQ4568089

Joanna Sokół, Krzysztof Węsek, Paweł Rzążewski, Konstanty Junosza-Szaniawski

Publication date: 15 June 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1097821

zbMATH Keywords

online algorithms; coloring; \(L(2,1)\)-labeling; unit disk intersection graphs

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

68W27: Online algorithms; streaming algorithms

Related Items

Unnamed Item, Online coloring a token graph, \( L ( 2 , 1 )\)-labeling of disk intersection graphs, On the universality and extremality of graphs with a distance constrained colouring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fractional and \(j\)-fold coloring of the plane
• On distance constrained labeling of disk graphs
• The \(L(2,1)\)-labeling of \(K_{1,n}\)-free graphs and its applications
• Unit disk graphs
• \(T\)-colorings of graphs: recent results and open problems
• Unit disk graph recognition is NP-hard
• On coloring unit disk graphs
• \(\varepsilon\)-unit distance graphs
• On the \(L(p,1)\)-labelling of graphs
• Chromatic Number of the Plane & Its Relatives, History, Problems and Results: An Essay in 11 Parts
• Labelling Graphs with a Condition at Distance 2
• Topics in Intersection Graph Theory
• Graph labeling and radio channel assignment
• A Theorem about the Channel Assignment Problem
• Approximations for  -Colorings of Graphs
• The $L(2,1)$-Labeling Problem on Graphs