An official website of the United States government
Quasiplanar graphs, string graphs, and the Erdos-Gallai problem
- Award ID(s):
- 1800746
- PAR ID:
- 10444754
- Date Published:
- Journal Name:
- Graph Drawing and Network Visualization. GD 2022. Lecture Notes in Computer Science
- Volume:
- 13764
- Page Range / eLocation ID:
- 219-231
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Given any graph G G , the spread of G G is the maximum difference between any two eigenvalues of the adjacency matrix of G G . In this paper, we resolve a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs. The first states that for all positive integers n n , the n n -vertex graph G G that maximizes spread is the join of a clique and an independent set, with ⌊ 2 n / 3 ⌋ \lfloor 2n/3 \rfloor and ⌈ n / 3 ⌉ \lceil n/3 \rceil vertices, respectively. Using techniques from the theory of graph limits and numerical analysis, we prove this claim for all n n sufficiently large. As an intermediate step, we prove an analogous result for a family of operators in the Hilbert space over L 2 [ 0 , 1 ] \mathscr {L}^2[0,1] . The second conjecture claims that for any fixed m ≤ n 2 / 4 m \leq n^2/4 , if G G maximizes spread over all n n -vertex graphs with m m edges, then G G is bipartite. We prove an asymptotic version of this conjecture. Furthermore, we construct an infinite family of counterexamples, which shows that our asymptotic solution is tight up to lower-order error terms.more » « less
-
Abstract It was conjectured by Hajós that graphs containing no ‐subdivision are 4‐colorable. Previous results show that any possible minimum counterexample to Hajós' conjecture, called Hajós graph, is 4‐connected but not 5‐connected. In this paper, we show that if a Hajós graph admits a 4‐cut or 5‐cut with a planar side then the planar side must be small or contains a special wheel. This is a step in our effort to reduce Hajós' conjecture to the Four Color Theorem.more » « less
-
Abstract It is widely recognized that we need to prepare students to think with data. This study investigates student interactions with digital data graphs and seeks to identify what might prompt them to shift toward using their graphs as thinking tools in the authentic activity of doing science. Drawing from video screencast data of three small groups engaged in sensor‐based and computer simulation‐based experiments in high school physics classes, exploratory qualitative methods are used to identify the student interactions with their graphs and what appeared to prompt shifts in those interactions. Analysis of the groups, one from a 9th grade class and two from 11th/12th grade combined classes, revealed that unexpected data patterns and graphical anomalies sometimes, but not always, preceded deeper engagement with the graphs. When shifts toward deeper engagement did occur, transcripts revealed that the students perceived the graphical patterns to be misaligned with the actions they had taken to produce those data. Misalignments between the physical, digital, and conceptual worlds of the investigations played an important role in these episodes, appearing to motivate students to revise either their experimental procedures or their conceptions of the phenomena being explored. If real‐time graphs can help foster a sense in students that there should be alignments between their data production and data representations, it is suggested that pedagogy leverage this as a way to support deeper student engagement with graphs.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-031-22203-0_16
