\(k\)-critical graphs in \(P_5\)-free graphs
From MaRDI portal
Publication:5918256
DOI10.1007/978-3-030-58150-3_33zbMath1502.05058OpenAlexW3131111727MaRDI QIDQ5918256
Yongtang Shi, Jan Goedgebeur, Kathie Cameron, Shenwei Huang
Publication date: 21 April 2021
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-58150-3_33
Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
- Complexity of coloring graphs without paths and cycles
- Ore's conjecture on color-critical graphs is almost true
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- The strong perfect graph theorem
- \(K_{4}\)-free graphs with no odd holes
- Efficient secure two-party protocols. Techniques and constructions
- Some results on graphs without long induced paths
- Paw-free graphs
- From obfuscation to the security of Fiat-Shamir for proofs
- Critical \((P_6, \mathrm{banner})\)-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- The chromatic number of \(\{P_5,K_4\}\)-free graphs
- Noninteractive zero knowledge for NP from (Plain) Learning With Errors
- Constructions of \(k\)-critical \(P_5\)-free graphs
- Obstructions for three-coloring graphs without induced paths on six vertices
- Vertex-critical \((P_5\), banner)-free graphs
- Certifying coloring algorithms for graphs without long induced paths
- A decomposition theorem for partially ordered sets
- Note on the colouring of graphs
- Fiat–Shamir for Highly Sound Protocols Is Instantiable
- Security Proofs for Signature Schemes
- Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures
- A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems
- Publicly Verifiable Non-Interactive Zero-Knowledge Proofs
- A new identification scheme based on syndrome decoding
- The knowledge complexity of interactive proof-systems
- The Cramer-Shoup Strong-RSA Signature Scheme Revisited
- Exhaustive generation of k‐critical ‐free graphs
- On $3$-Colorable $P_5$-Free Graphs
- Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs
- An Efficient Transform from Sigma Protocols to NIZK with a CRS and Non-programmable Random Oracle
- Advances in Cryptology – CRYPTO 2004
- On Seed-Incompressible Functions
- A Dual of Dilworth's Decomposition Theorem
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- Some Theorems on Abstract Graphs
