Online coloring and L(2,1)-labeling of unit disk intersection graphs

DOI10.1137/16M1097821MaRDI QIDQ4568089zbMATH OpenOpenAlexWikidataFDO

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

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 algorithmscoloring\(L(2,1)\)-labelingunit disk intersection graphs

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• On-line coloring of geometric intersection graphs
• \( L ( 2 , 1 )\)-labeling of disk intersection graphs
• A 116/13-approximation algorithm for \(L(2,1)\)-labeling of unit disk graphs
• Independence and Coloring Problems on Intersection Graphs of Disks
• Structural Information and Communication Complexity

Cites work

• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1769307 (Why is no real title available?)
• scientific article; zbMATH DE number 881282 (Why is no real title available?)
• scientific article; zbMATH DE number 1420920 (Why is no real title available?)
• A Theorem about the Channel Assignment Problem
• Approximations for  -Colorings of Graphs
• Chromatic number of the plane \& its relatives, history, problems and results: an essay in 11 parts
• Fractional and \(j\)-fold coloring of the plane
• Graph labeling and radio channel assignment
• Labelling Graphs with a Condition at Distance 2
• On coloring unit disk graphs
• On distance constrained labeling of disk graphs
• On the \(L(p,1)\)-labelling of graphs
• The $L(2,1)$-Labeling Problem on Graphs
• The \(L(2,1)\)-labeling of \(K_{1,n}\)-free graphs and its applications
• Topics in Intersection Graph Theory
• Unit disk graph recognition is NP-hard
• Unit disk graphs
• \(T\)-colorings of graphs: recent results and open problems
• \(\varepsilon\)-unit distance graphs

Cited in

(11)

• Online coloring a token graph
• Structural Information and Communication Complexity
• scientific article; zbMATH DE number 1877050 (Why is no real title available?)
• Online coloring of short intervals
• \( L ( 2 , 1 )\)-labeling of disk intersection graphs
• A tight bound for online colouring of disk graphs
• On distance constrained labeling of disk graphs
• Online coloring of disk graphs
• scientific article; zbMATH DE number 7758354 (Why is no real title available?)
• Online \(L(2,1)\)-coloring problem on paths with restricted size of memory
• On the universality and extremality of graphs with a distance constrained colouring

This page was built for publication: Online coloring and \(L(2,1)\)-labeling of unit disk intersection graphs

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